package com.mrzhou.study.struct.sort;

import com.mrzhou.core.tool.utils.DataUtil;

/**
 * 排序算法之希尔排序
 */
public class ShellSort {

    public static void main(String[] args) {
        for(int j = 0; j < 5; j++) {
            int arr[] = new int[9000000];
            /*{8, 9, 1, 7, 2, 3, 5, 4, 6, 0};*/

            for(int i = 0; i < arr.length; i++) {
                arr[i] = DataUtil.randomInt(0, arr.length);
            }
            Long startTime = System.currentTimeMillis();
            ShellSort.sort(arr);
            Long endTime = System.currentTimeMillis();
//        System.out.println(InsertionSort.toString(arr, 20));
            System.out.printf("希尔排序[%d]条数据, 花费的时间: %d\n", arr.length, (endTime - startTime));
        }
    }

    /**
     * 个人实现;
     *  90000条5次执行时间:   26, 28, 28, 25, 21
     *  900000条5次执行时间: 277, 250, 239, 246, 235
     */
    public static void sort(int arr[]) {
        int gap = arr.length;
        int flag = 0;
        while(true) {
            if(flag == 0) {
                gap = gap / 2;
                flag = gap;
            }

            for(int i = flag - 1; i + gap < arr.length; i+=gap) { // 看了下视频代码, 这里初始i可以直接为gap, 先上加一直到arr.length-1处停止, 这样就不用flag变量了
                int temp = arr[i + gap]; // 如果i=gap的话, 那么就应该用i-gap
                int j = i;
                while(j >= 0 && temp < arr[j]) { // 从小到大排
                    arr[j+gap] = arr[j];
                    j-=gap; // j = j - gap;
                }
                arr[j+gap] = temp;
            }

            if(gap == 1) {  // 增量gap == 1 时跳出循环, 排序结束
                break;
            } else {
                flag--;
            }
        }
    }

    /**
     * 视频实现的代码
     *      90000条5次执行时间:   34, 30, 39, 33, 22
     *      900000条5次执行时间:  238, 197, 189, 195, 193
     *      900000条5次执行时间:  2857, 3041, 2957, 2348, 2300
     */
    public static void videoSort(int[] arr ){
        for(int gap = arr.length/2; gap > 0; gap/=2) {
            for(int i = gap; i < arr.length; i++) { // 从gap等于5的时候开始排序
                int j = i;
                int temp = arr[i]; // 取出当前i的元素为无序表的第一个元素
                if(arr[j] < arr[j - gap]) {
                    while(j - gap >= 0 && temp < arr[j - gap]) { // arr[j - gap] 为有效表的末尾元素
                        arr[j] = arr[j-gap];
                        j -= gap;
                    }
                    arr[j] = temp;
                }
            }
        }
    }


}
